"""
给定一个二叉树，返回其节点值自底向上的层序遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）
"""
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def levelOrderBottom(self, root):
        def bfs(level):
            tmp = []
            if not level: return
            for i in range(len(level)):
                node = level.pop()
                if not node: continue
                tmp.append(node.val)
                if node.left: level.insert(0, node.left)
                if node.right: level.insert(0, node.right)
            if tmp: result.insert(0, tmp)
            bfs(level)
        result = []
        bfs([root])
        return result